#!/usr/bin/python
# -*- coding:utf-8 -*-
#冒泡排序
#@author: wklken@yeah.net
#2012-05-05
#此处冒泡 从小到大排序，所以每次最大的会冒泡到序列最后一个
#print信息可删除 ,cmp信息记录比较次数，可删除

#冒泡排序，base
def bubble(l):
  print l
  cmp = 0
  for i in range(len(l)-1,0,-1):
    #每一轮冒泡，第 i个 元素会是最大的(i<=size-1)
    for j in range(i):
      print "cmp",l[j],l[j+1],
      #从0到i-1,比较 current 和next,若current > next，对换
      cmp += 1
      if l[j] > l[j+1]:
        l[j], l[j+1] = l[j+1], l[j]
        print "-> change",l
      else:
        print "-> nochange"
    print l
  print "cmp count",cmp
  

#改进1:  当某一轮跑完，不存在数据交换时，代表已排序完成，此时退出

def bubble_improve(l):
  print l
  cmp = 0
  flag = 1 #初始标志，1
  for i in range(len(l)-1,0,-1):
    #若是上一轮存在数据交换，继续执行排序
    if flag:
      flag = 0 #每一轮初始，交换标志为0
      for j in range(i):
        print "cmp",l[j],l[j+1],
        cmp += 1
        if l[j] > l[j+1]:
          l[j], l[j+1] = l[j+1], l[j]
          flag = 1 #存在交换，标志置为1
          print "-> change",l
        else:
          print "-> nochange"
      print l
    #否则，代表目前序列已经排序完毕了
    else:
      break
  print "cmp count",cmp

#改进2: 局部冒泡排序
def bubble_improve2(l):
  print l
  cmp = 0
  flag = 1
  scope = len(l)-1
  for i in range(scope,0,-1):
    if flag: 
      flag = 0
      for j in range(i):
        print "cmp",l[j],l[j+1],
        cmp += 1
        inner_flag = 0 #本次是否存在数据交换标志，每次置空，不复用flag的原因是如果第一次就交换了，会造成不必要的局部冒泡
        if l[j] > l[j+1]:
          l[j], l[j+1] = l[j+1], l[j]
          flag = 1
          inner_flag = 1
          print "-> change",l
        else:
          print "-> nochange"
        #从前往后的冒泡，j与j+1发生数据交换了,反向冒泡 j-1 j
        #若是本轮存在数据交换，局部排序处理 j-1  j j+1，保证是从小到大的 
        if inner_flag:
          if j - 1 > 0:
            print "inner cmp",l[j-1],l[j]
            cmp += 1
            if l[j-1] > l[j]:
              l[j-1], l[j] = l[j],l[j-1]
              print "inner change",l
      print l
    else:
      break
  print "cmp count",cmp


l = [ 50,10,30,20,40,60 ]
print "base bubble sort:"
bubble(l)
print ""

#l = [ 50,10,30,20,40,60 ]
l = [ 50,10,30,20,40,60 ]
print "improve bubble sort:"
bubble_improve(l)
print ""


#l = [ 50,10,30,20,40,60 ]
l = [ 50,10,30,20,40,60 ]
print "improve bubble sort2:"
bubble_improve2(l)
